package ch09_;

import java.util.Arrays;
import java.util.Random;

public class Ch9_3 {
	public static int magic1(int[] A, int l, int r) {
		if (l > r) return -1;
		int mid = ((l + r) >> 1);
		if (mid == A[mid]) return mid;
		else if (mid < A[mid]) {
			return magic1(A, l, mid - 1);
		} else {
			return magic1(A, mid + 1, r);
		}
	}
	
	public static int magic2(int[] A, int l, int r) {
		if (l > r) return -1;
		int mid = ((l + r) >> 1);
		if (mid == A[mid]) return mid;
		int left = -1;
		if (A[l] < mid) {
			left = magic2(A, l, mid - 1);
			if (left != -1) {
				return left;
			}
		}
		int right = -1;
		if (A[r] > mid) {
			right = magic2(A, mid + 1, r);
		}
		return right;
	}
	
	public static void main(String[] args) {
		/*
		 * q1
		 */
		//int[] A = {1, 2, 4, 6, 8, 10};
		//System.out.println(magic1(A, 0, A.length - 1));
		
		int limit = 10;
		int[] A2 = new int[limit];
		Random r = new Random();
		for (int i = 0; i < limit; i++) {
			A2[i] = r.nextInt((int)(limit * 1.0));
		}
		Arrays.sort(A2);
		System.out.println(Arrays.toString(A2));
		System.out.println(magic2(A2, 0, A2.length - 1));
	}
}
